\newpage

\section{Quantitative Analysis of Join Efficiency}
In practice, the effective CPU utilization for join processing is inversely proportional to the number of comparison operations contributing to join outputs. So we define the join processing efficiency $\mathcal{P}$ as 

\begin{equation*}
\mathcal{P} = \dfrac{number\ of\ outputs}{number\ of\ comparisons}
\end{equation*}

\noindent
And we will show that S2J's join processing using in-memory index is much more efficient than the approach by brute-force pairwise comparison.

Let $r$ and $s$ be the instant tuple amounts of two opposite streams (assuming $r \geq s$) in a worker, and $\kappa$ be the output amount of joining these tuples. Thus the efficiency of processing join via brute-force pairwise comparison is 

\begin{equation*}
\mathcal{P}_{bf} = \dfrac{\kappa}{r \cdot s}
\end{equation*}

\noindent
It is often the case that $\kappa \ll r \times s$, leading to $\mathcal{P}_{bf} \ll 1$. For example, $r=500$, $s=400$ and $\kappa=100$ imply $\mathcal{P}_{bf}=0.0005$, indicating that only 0.05\% of the CPU utilization for the join processing is effective.

S2J introduces in-memory BST- and hash-based indices to accelerate the processing of non-equi-join and equi-join, respectively. The keys maintained in the index are the join keys of the relevant predicate. When a tuple arrives at the worker, it searches the index for the satisfying keys and, if found, joins with the tuples associated with those keys. The searching takes $O(\log n)$ time for BST and $O(1)$ time for hash table, and joining with associated tuples takes linear time. Note that the domain distribution of join key values affects the efficiency of such search-and-join processing. Let $\eta$ be the maximum number of tuples associating with a join key value in both streams. The efficiency of processing non-equi-join via BST-based index is 

%We will show that such search-and-join approach greatly improves the join processing efficiency.

%The efficiency of search-and-join processing is affected by the domain distribution of join key values. 

\begin{equation*}
\mathcal{P}_{bst} 
= \dfrac{\kappa}{r \cdot O(\log s) + s \cdot O(\log r) + \kappa} 
\geq \dfrac{\kappa}{r \cdot (O(\log r) + \eta)}
\end{equation*}

\noindent
Comparing with the brute-force approach, we have

\begin{equation*}
\dfrac{\mathcal{P}_{bst}}{\mathcal{P}_{bf}} \geq \dfrac{s}{O(\log r) + \eta}
\end{equation*}

\noindent
In real applications, if the tuples are not highly skewed w.r.t. the join key making $\eta=O(\log r)$, then $\mathcal{P}_{bst}$ outweights $\mathcal{P}_{bf}$ with a $O(\dfrac{s}{\log r})$ factor. The improvement could be remarkable when the workload is sufficently large.

%and the input is sufficiently large (e.g., $s=\Omega(\log r)$), then 

Similarly, the efficiency of processing equi-join via hash-based index is 

\begin{equation*}
\mathcal{P}_{hash} = \dfrac{\kappa}{r \cdot O(1) + s \cdot O(1) + \kappa}
	\geq \dfrac{\kappa}{r \cdot (C_{hash} + \eta)}
\end{equation*}

\noindent
where $C_{hash}$ is the constant hidden in the big-O. And the comparison against the brute-force approach is 

\begin{equation*}
\dfrac{\mathcal{P}_{hash}}{\mathcal{P}_{bf}} \geq \dfrac{s}{C_{hash} + \eta}
\end{equation*}

If the hash function is good enough to restrict $\eta \leq C_{hash}$, the hash-based index brings significant improvement of efficiency for joining sufficiently large inputs (i.e., $C_{hash} \ll s$).
